#define _CRT_SECURE_NO_WARNINGS
class Solution {
public:
    TreeNode* dfs(vector<int>& nums, int left, int right)
    {
        if (left > right) return nullptr;
        int mid = (right - left) / 2 + left;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = dfs(nums, left, mid - 1);
        root->right = dfs(nums, mid + 1, right);
        return root;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        TreeNode* root = dfs(nums, 0, nums.size() - 1);
        return root;
    }
};
